package com.tree.TreeBaseOnArray;

public class TreeBaseOnArray {
	private class Node{
		private String data;
		private int parent;
		public Node(String data, int parent) {
			super();
			this.data = data;
			this.parent = parent;
		}
		public Node(String data) {
			super();
			this.data = data;
		}
		
		public String getData() {
			return data;
		}
		public void setData(String data) {
			this.data = data;
		}
		public int getParent() {
			return parent;
		}
		public void setParent(int parent) {
			this.parent = parent;
		}
		@Override
		public String toString() {
			return "Node [data=" + data + ", parent=" + parent + "]";
		}
	}
	
	private int treeSize;
	private final int DEFAULT_TREESIZE=100;
	private Node[] treeNodes;
	private int nodeCount;
	
	public TreeBaseOnArray(int treeSize,String root) {
		super();
		this.treeSize = treeSize;
		treeNodes=new Node[treeSize];
		Node node=new Node(root, -1);
		treeNodes[0]=node;
		nodeCount++;
	}
	
	public TreeBaseOnArray() {
		super();
		treeSize=DEFAULT_TREESIZE;
		treeNodes=new Node[DEFAULT_TREESIZE];
	}

	public boolean empty(){
		return nodeCount>0?true:false;
	}
	
	public boolean addNode(String parent,String data){
		int parentPos=getNodePosition(parent);
		Node node=new Node(data, parentPos);
		if(treeSize>nodeCount){
			treeNodes[nodeCount++]=node;
			return true;
		}else{
			return false;
		}
	}
	
	public Node getParent(String nodeData){
		int nodePos=getNodePosition(nodeData);
		int parentNodePos=treeNodes[nodePos].getParent();
		return parentNodePos>0?treeNodes[parentNodePos]:treeNodes[nodePos];
		
	}
	
	public int getNodePosition(String parent){
		for (int i = 0; i < treeNodes.length; i++) {
			if(treeNodes[i].getData().equals(parent))
				return i;
		}
		
		return 0;
	}
	
	public Node[] getNodeChildren(String nodeData){
		int parentPos=getNodePosition(nodeData);
		Node[] children=new Node[DEFAULT_TREESIZE];
		int count=0;
		for (int i = 0; i < nodeCount; i++) {
			if(treeNodes[i].getParent()==parentPos){
				children[count++]=treeNodes[i];
			}
		}
		return children;
	}
	
	public Node getSpecifiedNode(String parentData,int num){
		Node[] children=getNodeChildren(parentData);
		if(children.length>num){
			return children[num];
		}else {
			return null;
		}
	}
	
	public int treeDepth(){
		int depth=nodeDeep(treeNodes[0], 1);
		return depth;
	}
	
	private int nodeDeep(Node node,int depth){
		Node[] childrenNodes=getNodeChildren(node.getData());
		int temp=0;
		
		for (Node node2 : childrenNodes) {
			if(null!=node2){
				int deep=nodeDeep(node2, depth+1);
				if(deep>temp)
					temp=deep;
			}
		}
		return depth>temp?depth:temp;
	}
}
